% Ejercicio "Matrices en MATLAB"
\subsection*{\fbox{\theejercicio} - Matrices en MATLAB}

En un lenguaje de programaci\'on orientado al c\'alculo matricial es posible describir directamente operaciones entre matrices de dos dimensiones, y entre \'estas y escalares.

\par Para escribir una matriz en este lenguaje se escriben los elementos de cada fila separados por comas, y las filas separadas por punto y coma y delimitadas mediante corchetes. Es decir, para escribir en este lenguaje la matriz de 2 $\times$ 3:

\[
\left[
\begin{array}{ccc}
1 & 2 \\
3 & 4 \\
5 & 6 \\
\end{array}
\right]
\]

se emplea la notaci\'on:

\begin{center}
\verb@[1,2; 3,4; 5,6]@
\end{center}

Para sumar dos matrices, es suficiente yustaponerlas al signo de operaci\'on de la suma:

\begin{center}
\verb@[1,2; 3,4; 5,6] + [7,8; 9,10; 11,12]@
\end{center}

y de forma similar pueden pueden realizarse las operaciones b\'asicas de resta y multiplicaci\'on. Asi mismo, son v\'alidas en el lenguajes las cuatro operaciones básicas entre matrices y escalares, o entre escalares y matrices, (y por supuesto, entre escalares y escalares). Por ejemplo:

\begin{center}
\verb@7 + [1,2; 3,4]@
\end{center}

Las expresiones de operaciones entre matrices y/o escalares pueden agruparse dando lugar a expresiones m\'as complejas, en las que pueden emplearse par\'entesis seg\'un su uso habitual para indicar la prioridad de las operaciones, por ejemplo:

\begin{center}
\verb@( [1,2; 3,4] + [5,6; 7,8] ) * [9,10; 11,12]@
\end{center}

\begin{enumerate}[1)]
\item Definir una gram\'atica de contexto libre  que describa el lenguaje de las expresiones matriciales.
\item Hallar una gram\'atica equivalente a la anterior que cumpla la condici\'on LL(1), construyendo para ella las tablas de an\'alisis sint\'actico.
\item Construir un programa en C y en LEX, implementando la t\'ecnica LL(1), para realizar el reconocimiento sint\'actico de las expresiones de suma y producto de matrices. La salida del programa es simplemente si la cadena pertenece o no al lengujae, y el mensaje de error correspondiente en caso de que no pertenezca.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

Se pueden definir los tokens:

\begin{center}
\begin{tabular}{ll}
{\it ABREPAR}   & (                     \\
{\it CIERRAPAR} & )                     \\
{\it ABRECOR}   & [                     \\
{\it CIERRACOR} & ]                     \\
{\it MAS}       & +                     \\
{\it POR}       & *                     \\
{\it NUMERO}    & 12345                 \\
{\it COMA}      & ,                     \\
{\it PYC}       & ;                     \\
{\it EOF}       & \$ (final de fichero) \\
\end{tabular}
\end{center}

Con lo que una posible gram\'atica del analizador sint\'actico puede definirse como:

\begin{center}
\begin{tabular}{|lcl|} \hline
                  &               &                                                 \\
{\em Expresi\'on} & $\rightarrow$ & {\em Expresi\'on} {\it MAS} {\em T\'ermino}     \\
                  & $|$           & {\em T\'ermino}                                 \\
{\em T\'ermino}   & $\rightarrow$ & {\em Expresi\'on} {\it POR} {\em Factor}        \\
                  & $|$           & {\em Factor}                                    \\
{\em Factor}      & $\rightarrow$ & {\em Matriz}                                    \\
                  & $|$           & {\it ABREPAR} {\em Expresi\'on} {\it CIERRAPAR} \\
                  & $|$           & {\it NUMERO}                                    \\
{\em Matriz}      & $\rightarrow$ & {\it ABRECOR} {\em ListaFilas} {\it CIERRACOR}  \\
{\em ListaFilas}  & $\rightarrow$ & {\em ListaFilas} {\it PYC} {\em Fila}           \\
                  & $|$           & {\em Fila}                                      \\
{\em Fila}        & $\rightarrow$ & {\em Fila} {\it COMA NUMERO}                    \\
                  & $|$           & {\it NUMERO}                                    \\
                  &               &                                                 \\ \hline
\end{tabular}
\end{center}

Esta gram\'atica no es LL(1).

Apartado 2)

\begin{center}
\begin{tabular}{|lcl|l|} \hline
{\bf Regla}            &               &                                                 & {\bf S\'{\i}mbolos directores} \\ \hline
{\em Expresi\'on}      & $\rightarrow$ & {\em T\'ermino Resto Expresi\'on}               & {\it ABREPAR ABRECOR NUMERO}   \\ \hline
{\em RestoExpresi\'on} & $\rightarrow$ & {\it MAS} {\em T\'ermino Resto Expresi\'on}     & {\it MAS}                      \\ \hline
                       & $|$           & $\varepsilon$                                   & {\it CIERRAPAR EOF}            \\ \hline
{\em T\'ermino}        & $\rightarrow$ & {\em Factor Resto T\'ermino}                    & {\it ABREPAR ABRECOR NUMERO}   \\ \hline
{\em RestoT\'ermino}   & $\rightarrow$ & {\it POR} {\em T\'ermino Resto T\'ermino}       & {\it POR}                      \\ \hline
                       & $|$           & $\varepsilon$                                   & {\it MAS CIERRAPAR EOF}        \\ \hline
{\em Factor}           & $|$           & {\em Matriz}                                    & {\it ABRECOR}                  \\ \hline
                       & $|$           & {\it ABREPAR} {\em Expresi\'on} {\it CIERRAPAR} & {\it ABREPAR}                  \\ \hline
                       & $|$           & {\it NUMERO}                                    & {\it NUMERO}                   \\ \hline
{\em Matriz}           & $\rightarrow$ & {\it ABRECOR} {\em ListaFilas} {\it CIERRACOR}  & {\it ABRECOR}                  \\ \hline
{\em ListaFilas}       & $\rightarrow$ & {\em Fila RestoListaFilas}                      & {\it NUMERO}                   \\ \hline
{\em RestoListaFilas}  & $\rightarrow$ & {\it PYC} {\em Fila RestoListaFilas}            & {\it PYC}                      \\ \hline
                       & $|$           & $\varepsilon$                                   & {\it CIERRACOR}                \\ \hline
{\em Fila}             & $\rightarrow$ & {\it NUMERO} {\em RestoFila}                    & {\it NUMERO}                   \\ \hline
{\em RestoFila}        & $\rightarrow$ & {\it COMA NUMERO} {\em RestoFila}               & {\it COMA}                     \\ \hline 
                       & $|$           & $\varepsilon$                                   & {\it PYC CIERRACOR}            \\ \hline
\end{tabular}
\end{center}

Apartado 3)

\underline{Analizador l\'exico en LEX}:

\begin{verbatim}
%{
#include "mat.h" 
%}

%%
\(             { return ABREPAR; }
\)             { return CIERRAPAR; }
\[             { return ABRECOR; }
\]             { return CIERRACOR; }
\+             { return MAS; }
\*             { return POR; }
\,             { return COMA; }
\;             { return PYC; }
0|[1-9][0-9]*  { return NUMERO; }
[\ \n\t]       {;}
.              { ; /* error */ }
\end{verbatim}

\underline{Analizador sint\'actico en C}:

\begin{verbatim}
int main() {
   token = yylex();
   expresion();
   if (token == EOF) 
      printf("Se ha reconocido una expresion de matrices correcta\n"); 
}

void expresion() {
   switch(token) {
     case ABREPAR:
     case ABRECOR:
     case NUMERO:
        termino();
        restoexpresion();
        break;
     default:
         printf("Se esperaba ABRECOR, ABREPAR o NUMERO\n");
   }
}

void restoexpresion() {
   switch(token) {
     case MAS:
        if (token==MAS) token = yylex();
        termino();
        restoexpresion();
        break;
     case CIERRAPAR:
     case EOF:
        break;
     default:
        printf("Se esperaba MAS o CIERRAPAR o EOF\n");
   }
}

void termino() {
   switch(token) {
     case ABREPAR:
     case ABRECOR:
     case NUMERO:
        factor();
        restotermino();
        break;
     default:
         printf("Se esperaba ABRECOR, ABREPAR o NUMERO\n");
   }
}

void restotermino() {
   switch(token) {
     case POR:
        if (token==POR) token = yylex();
        factor();
        restotermino();
        break;
     case MAS:
     case CIERRAPAR:
     case EOF:
        break;
     default:
        printf("Se esperaba MAS o POR o CIERRAPAR o EOF\n");
   }
}

void factor() {
   switch(token) {
     case ABREPAR:
         if (token==ABREPAR) token = yylex();
         expresion();
         if (token==CIERRAPAR) token = yylex();
         break;
     case ABRECOR:
         matriz();
         break;
     case NUMERO:
         if (token==NUMERO) token = yylex();
         break;
     default:
         printf("Se esperaba ABREPAR o ABRECOR o NUMERO\n");
   }
}

void matriz() {
   switch(token) {
     case ABRECOR:
         if (token==ABRECOR) token = yylex();
         listafilas();
         if (token==CIERRACOR) token = yylex();
         break;
     default:
         printf("Se esperaba ABRECOR\n");
   }
}

void listafilas() {
   switch(token) {
     case NUMERO:
         fila();
         restolistafilas();
         break;
     default:
         printf("Se esperaba NUMERO\n");
   }
}

void restolistafilas() {
   switch(token) {
     case PYC:
         if (token==PYC) token = yylex();
         fila();
         restolistafilas();
         break;
     case CIERRACOR:
         break;
     default:
         printf("Se esperaba PYC o CIERRACOR\n");
   } 
}

void fila() {
   switch(token) {
     case NUMERO:
         if (token==NUMERO) token = yylex();
         restofila();
         break;
     default:
         printf("Se esperaba NUMERO\n");
   }
}

void restofila() {
   switch(token) {
     case COMA:
         if (token==COMA) token = yylex();
         if (token==NUMERO) token = yylex();
         restofila();
         break;
     case PYC:
     case CIERRACOR:
         break;
     default:
         printf("Se esperaba COMA , PYC o CIERRACOR\n");
   }
}
\end{verbatim}